{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Pairs of Equal Substrings With Minimum Difference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countQuadruples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计距离最小的子串对个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>输入数据为两个字符串<code>firstString</code> 和 <code>secondString</code>，两个字符串下标均从0开始，且均只包含小写的英文字符，请计算满足下列要求的下标四元组<code>(i,j,a,b)</code>的个数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 <= i <= j < firstString.length</code></li>\n",
    "\t<li><code>0 <= a <= b < secondString.length</code></li>\n",
    "\t<li><code>firstString</code>字符串中从<code>i</code>位置到<code>j</code>位置的子串(包括<code>j</code>位置的字符)和<code>secondString</code>字符串从<code>a</code>位置到<code>b</code>位置的子串(包括<code>b</code>位置字符)相等</li>\n",
    "\t<li><code>j-a</code>的数值是所有符合前面三个条件的四元组中可能的最小值</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回符合上述 4 个条件的四元组的 <strong>个数</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>firstString = \"abcd\", secondString = \"bccda\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>(0,0,4,4)是唯一符合条件的四元组且其<code>j-a</code>的数值是最小的.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>firstString = \"ab\", secondString = \"cd\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>没有任何一个四元组能满足上述4个要求.\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= firstString.length, secondString.length <= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li>两个输入字符串均只包含小写英文字符.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-pairs-of-equal-substrings-with-minimum-difference](https://leetcode.cn/problems/count-pairs-of-equal-substrings-with-minimum-difference/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-pairs-of-equal-substrings-with-minimum-difference](https://leetcode.cn/problems/count-pairs-of-equal-substrings-with-minimum-difference/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcd\"\\n\"bccda\"', '\"ab\"\\n\"cd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruples(self, firstString: str, secondString: str) -> int:\n",
    "        fidx = {}\n",
    "        for idx, ch in enumerate(firstString):\n",
    "            if not ch in fidx:\n",
    "                fidx[ch] = idx\n",
    "        \n",
    "        minval = 2 ** 63\n",
    "        minvalcount = 0\n",
    "        for idx, ch in enumerate(secondString):\n",
    "            if ch in fidx:\n",
    "                t = -idx + fidx[ch]\n",
    "                if t < minval:\n",
    "                    minval = t\n",
    "                    minvalcount = 1\n",
    "                elif t == minval:\n",
    "                    minvalcount += 1\n",
    "        return minvalcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countQuadruples(self, firstString, secondString):\n",
    "        # 初始化两个字典来存储字符在两个字符串中的位置\n",
    "        dic1 = {}\n",
    "        dic2 = {}\n",
    "        \n",
    "        m, n = len(firstString), len(secondString)\n",
    "        \n",
    "        # 记录firstString中每个字符第一次出现的位置\n",
    "        for k in range(m):\n",
    "            if firstString[k] not in dic1:\n",
    "                dic1[firstString[k]] = k\n",
    "                \n",
    "        # 记录secondString中每个字符最后一次出现的位置\n",
    "        for v in range(n):\n",
    "            dic2[secondString[v]] = v\n",
    "            \n",
    "        stack = []\n",
    "        \n",
    "        # 去除firstString中重复的字符\n",
    "        fs = list(set(firstString))\n",
    "        \n",
    "        # 查找满足条件的四元组，并将结果存入stack中\n",
    "        for f in fs:\n",
    "            if f in dic2:\n",
    "                stack.append(dic1[f] - dic2[f])\n",
    "            else:\n",
    "                continue\n",
    "                \n",
    "        # 如果stack为空，返回0，否则返回满足条件的四元组个数\n",
    "        if not len(stack):\n",
    "            return 0\n",
    "        else:\n",
    "            return len([u for u in stack if u == min(stack)])\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.countQuadruples(\"abcdef\", \"fedcba\"))  # 输出应为 6\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countQuadruples(self, firstString, secondString):\n",
    "        dic1 = {}\n",
    "        dic2 = {}\n",
    "        m, n = len(firstString), len(secondString)\n",
    "        for k in range(m): # 第一次出现\n",
    "            if firstString[k] not in dic1:\n",
    "                dic1[firstString[k]] = k\n",
    "        for v in range(n): # 最后一次出现\n",
    "            dic2[secondString[v]] = v\n",
    "        stack = []\n",
    "        fs = list(set(firstString)) # 注意这里需要哈希，避免firststring后续出现同样的字母\n",
    "        for f in fs:\n",
    "            if f in dic2:\n",
    "                stack.append(dic1[f]-dic2[f])\n",
    "            else:\n",
    "                continue\n",
    "        if not len(stack):return 0\n",
    "        else: \n",
    "            return len([u for u in stack if u == min(stack)])    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countQuadruples(self, firstString, secondString):\n",
    "        dic1 = {}\n",
    "        dic2 = {}\n",
    "        m, n = len(firstString), len(secondString)\n",
    "        for k in range(m): # 第一次出现\n",
    "            if firstString[k] not in dic1:\n",
    "                dic1[firstString[k]] = k\n",
    "        for v in range(n): # 最后一次出现\n",
    "            dic2[secondString[v]] = v\n",
    "        stack = []\n",
    "        fs = list(set(firstString)) # 注意这里需要哈希，避免firststring后续出现同样的字母\n",
    "        for f in fs:\n",
    "            if f in dic2:\n",
    "                stack.append(dic1[f]-dic2[f])\n",
    "            else:\n",
    "                continue\n",
    "        if not len(stack):return 0\n",
    "        else: \n",
    "            return len([u for u in stack if u == min(stack)])    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from sortedcontainers import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruples(self, firstString: str, secondString: str) -> int:\n",
    "        g = defaultdict(list)\n",
    "\n",
    "        for i, x in enumerate(firstString):\n",
    "            g[x].append(i)\n",
    "        \n",
    "        dist = inf\n",
    "        for i, x in enumerate(secondString):\n",
    "            if g[x]: dist = min(dist, g[x][0] - i)\n",
    "        ans = 0\n",
    "\n",
    "        for i, x in enumerate(secondString):\n",
    "            if g[x] and g[x][0] - i == dist: ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruples(self, firstString: str, secondString: str) -> int:\n",
    "        fir, sec = defaultdict(list), defaultdict(list)\n",
    "        for i, j in enumerate(firstString):\n",
    "            fir[j].append(i)\n",
    "        for i, j in enumerate(secondString):\n",
    "            sec[j].append(i)\n",
    "        both = set(fir.keys()) & set(sec.keys())\n",
    "        if not both:\n",
    "            return 0\n",
    "        cnt = Counter()\n",
    "        for ch in both:\n",
    "            cnt[fir[ch][0] - sec[ch][-1]] += 1\n",
    "        mi = min(cnt.keys())\n",
    "        return cnt[mi]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 哈希+脑筋急转弯\n",
    "    # 题目有点绕，但是核心其实就是取尽可能小的j，和尽可能大的a，那么单个字符是最好的\n",
    "    # 遍历第一个字符去找最左边出现的字符的位置，第二个字符找最右边出现字符的位置\n",
    "    # 遍历左边的位置，去找对应的右边，计算j-a的差值，计算个数即是结果\n",
    "    def countQuadruples(self, firstString: str, secondString: str) -> int:\n",
    "        m, n = len(firstString), len(secondString)\n",
    "        first = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            first[firstString[i]].append(i)\n",
    "\n",
    "        second = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            second[secondString[i]].append(i)\n",
    "\n",
    "        dis = float(\"inf\")\n",
    "        for w in first:\n",
    "            if second[w]:\n",
    "                cur = first[w][0] - second[w][-1]\n",
    "                dis = dis if dis < cur else cur\n",
    "   \n",
    "        ans = 0\n",
    "        for w in first:\n",
    "            sec = set(second[w])\n",
    "            for i in first[w]:\n",
    "                if i - dis in sec:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
